\chapter{Método Simplex}
Uma dica é escolher uma das formas padrões (iremos escolher a forma de minimização) para trabalhar e sempre utilizá-la, isso é, quando um PL não estiver na forma escolhida transformá-lo. Espera-se que o leitor tenha notado que a transformação é uma operação barata.

Para os exercícios de Tableau encontra-se disponível ao leitor o solver presente em \url{http://www.zweigmedia.com/RealWorld/simplex.html} e o \textit{script} em python apresentado em \ref{PivoSimplex} que permite representarmos um PL na forma Tableau e executarmos algumas iterações.

\lstinputlisting[language=Python,label=PivoSimplex]{Codigos/PivoSimplexV1.py}

\begin{description}
	\item [3.1] Considere o PL
	\[
		\begin{array}{ll}
			\text{max } & \textbf{c}^T \textbf{x} \\
			\text{sa } & \mathbf{A}\mathbf{x} \leq \mathbf{b} \\
			& \mathbf{x} \geq \mathbf{0}
		\end{array}
	\]
	Suponha que o ponto $\mathbf{x}_0$ tal que $\mathbf{A}\mathbf{x}_0 < \mathbf{b}$ e $\mathbf{x}_0 > 0$. Mostre que $\mathbf{x}_0$ não pode ser solução ótima do PL.
	
	\begin{solution}
	Vamos colocar o PL na forma padrão de minimização:
	\[
		\begin{array}{ll}
			\text{min } & -\textbf{c}^T \textbf{x} \\
			\text{sa } & \mathbf{A}\mathbf{x} + \mathbf{1}\mathbf{s} = \mathbf{b} \\
			& \mathbf{x}, \mathbf{s} \geq \mathbf{0}
		\end{array}
	\]
	Como $\mathbf{A}\mathbf{x}_0 < \mathbf{b}$ e $\mathbf{x}_0 > 0$ temos que $\mathbf{s} > 0$ de modo que não estamos uma solução básica. Sabemos que a solução ótima é um ponto extremo e que todo ponto extremo está relacionado, a menos de degeneração, a uma única solução básica. Logo, como não estamos em uma solução básica não podemos estar no ótimo.
	\end{solution}
	
	\item [3.2] Considere o seguinte PL:
	\[
		\begin{array}{ll}
			\text{max } & x_1 + 3x_2 \\
			\text{sa } & -x_1 + x_2 \leq 4 \\
			& -x_1 + 2x_2 \leq 12 \\
			& x_1 + x_2 \leq 10 \\
			& x_1, x_2 \geq 0
		\end{array}
	\]
	\begin{enumerate}
		\item Desenhe a região factível e identifique a solução ótima.
		
		\begin{solution}
		Na Figura~\ref{fig:Ex3.2} encontra-se representado a região factível e a solução ótima é $(3,7)$.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=0.3,domain=-0.2:10.2]
			\fill[color=gray!20] (0,0) -- (0,4) -- (3,7) -- (10,0);
			
			\draw[very thin,color=gray] (-1.1,-1.1) grid (10.9,14.9);
			
			\draw[->] (-1.2,0) -- (11.2,0) node[right] {$x_1$};
			\draw[->] (0,-1.2) -- (0,15.2) node[above] {$x_2$};
			
			\clip (-1.2,-2.2) rectangle (20.2,16.2);

			\draw[color=blue] plot (\x,4+\x) node[below right] {$-x_1 + x_2 \leq 4$};
			\draw[color=red] plot (\x,0.5*12+0.5*\x) node[right] {$-x_1 + 2x_2 \leq 12$};
			\draw[color=green] plot (\x,10 - \x) node[below right] {$x_1 \geq -3$};

			\foreach \z in {12,18,...,30}{
			\draw[color=black] plot (\x,0.33*\z-0.33*\x) node[below right] {$z = \z$};
			}
			\end{tikzpicture}
			\caption{Região factível do exercício 3.2.} \label{fig:Ex3.2}
		\end{figure}
		\end{solution}
		
		\item Identifique todos os pontos extremos e reformule o problema em termos da combinação convexa destes.
		
		\begin{solution}
		Os pontos extremos são: $(0,0)$, $(0,4)$, $(3,7)$ e $(10,0)$. Deste modo podemos reescrever o PL como:
		\[
		\begin{array}{ll}
			\text{max } & 0\lambda_1 + 12\lambda_2 + 24\lambda_3 + 10\lambda_4 \\
			\text{sa } & \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 = 1\\
			& \lambda_1, \lambda_2, \lambda_3, \lambda_4 \geq 0
		\end{array}
		\]
		É fácil verificar que a solução é $\lambda_3 = 1$ e $\lambda_1 = \lambda_2 = \lambda_4 = 0$.
		\end{solution}
		
		\item Descarte a terceira restrição. Resolva novamente o problema.
		
		\begin{solution}
		Na Figura~\ref{fig:Ex3.2c} temos a representação da região factível ao descartar a terceira restrição.
		\begin{figure}[!h]
		\centering
		\begin{tikzpicture}[scale=0.3,domain=-0.2:10.2]
			\fill[color=gray!20] (0,0) -- (0,4) -- (4,8) -- (10.2,11.1) -- (10.2,0);
			
			\draw[very thin,color=gray] (-1.1,-1.1) grid (10.2,14.9);
			
			\draw[->] (-1.2,0) -- (10.6,0) node[right] {$x_1$};
			\draw[->] (0,-1.2) -- (0,15.2) node[above] {$x_2$};
			
			\clip (-1.2,-2.2) rectangle (20.2,16.2);

			\draw[color=blue] plot (\x,4+\x) node[below right] {$-x_1 + x_2 \leq 4$};
			\draw[color=red] plot (\x,0.5*12+0.5*\x) node[right] {$-x_1 + 2x_2 \leq 12$};

			\foreach \z in {12,18,...,42}{
			\draw[color=black] plot (\x,0.33*\z-0.33*\x) node[below right] {$z = \z$};
			}
		\end{tikzpicture}
		\caption{Região factível do exercício 3.2 ao retirar a terceira restrição.} \label{fig:Ex3.2c}
		\end{figure}
		
		Os pontos extremos são $(0,0)$, $(0,4)$ e $(4,8)$ e as direções extremas são $(1,0)$ e $(2,1)$. Deste modo podemos reescrever o PL como
		\[
		\begin{array}{ll}
			\text{max } & 0\lambda_1 + 12\lambda_2 + 24\lambda_3 + 10\lambda_4 + \mu_1 + 5\mu_2 \\
			\text{sa } & \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 = 1\\
			& \lambda_1, \lambda_2, \lambda_3, \lambda_4 \geq 0 \\
			& \mu_1, \mu_2 \geq 0
		\end{array}
		\]
		É fácil verificar que $\lambda_3 = 1$, $\lambda_1 = \lambda_2 = \lambda_4 = 0$ e $\mu_1, \mu_2 \geq 0$ é solução do PL.
		\end{solution}
		
		\item Os procedimentos utilizados nos itens anteriores são práticos para problemas de grande porte?
		
		\begin{solution}
		Não.
		\end{solution}
	\end{enumerate}
	
	\item [3.4] Considere o seguinte PL.
	\[
		\begin{array}{ll}
			\text{max} & 2x_1 + x_2 - x_3 \\
			\text{sa } & x_1 + x_2 + 2x_3 \leq 6 \\
			& x_1 + 4x_2 - x_3 \leq 4 \\
			& x_1, x_2, x_3 \geq 0
		\end{array}
	\]
	Encontre a solução ótima avaliando a função objetivo em todos os pontos extremos. Depois troque a primeira restrição por $x_1 + x_2 - 2x_3 \leq 6$ e resolva novamente o PL da mesma maneira.
	
	\begin{solution}
	Colocando o PL na forma padrão de minimização temos:
	\[
		\begin{array}{ll}
			\text{min} & -2x_1 - x_2 + x_3 \\
			\text{sa } & x_1 + x_2 + 2x_3 + x_4 = 6 \\
			& x_1 + 4x_2 - x_3 + x_5 = 4 \\
			& x_1, x_2, x_3, x_4, x_5 \geq 0
		\end{array}
	\]
	Temos como possibilidades para a solução básica:
	\begin{enumerate}
		\item $x_1$ e $x_2$ tal que $x_1 = \frac{20}{3}$ e $x_2 = -\frac{2}{3}$ que não é básica.
		\item $x_1$ e $x_3$ tal que $x_1 = \frac{14}{3}$ e $x_3 = \frac{2}{3}$ e portanto $z = -\frac{26}{3}$.
		\item $x_1$ e $x_4$ tal que $x_1 = 4$ e $x_4 = 2$ e portanto $z = -8$.
		\item $x_1$ e $x_5$ tal que $x_1 = 6$ e $x_5 = -2$ que não é básica.
		\item $x_2$ e $x_3$ tal que $x_2 = \frac{9}{10}$ e $x_3 = \frac{51}{20}$ e portanto $z = \frac{33}{20}$.
		\item $x_2$ e $x_4$ tal que $x_2 = 4$ e $x_4 = 2$ e portanto $z = -4$.
		\item $x_2$ e $x_5$ tal que $x_2 = 6$ e $x_5 = -20$ e portanto $z = -6$.
		\item $x_3$ e $x_4$ tal que $x_3 = -4$ e $x_4 = 14$ que não é básica.
		\item $x_3$ e $x_5$ tal que $x_3 = 3$ e $x_5 = 7$ e portanto $z = 3$.
		\item $x_4$ e $x_5$ tal que $x_4 = 6$ e $x_5 = 4$ e portanto $z = 0$.
	\end{enumerate}
	de ondo concluimos que $x_1 = \frac{14}{3}$, $x_3 = \frac{2}{3}$ e $x_2 = x_4 = x_5 = 0$ é a solução ótima.
	
	Utilizamos o mesmo método para o PL obtido ao substituir a primeira restrição por $x_1 + x_2 - 2x_3 \leq 6$.
	\end{solution}
	
	\item [3.5] Considere o seguinte PL:
	\[
		\begin{array}{ll}
			\text{max} & x_1 + 2x_2 + 4x_3 + 5x_5 + x_6 \\
			\text{sa } & 2x_1 + 6x_2 + 3x_3 + 2x_4 + 3x_5 + 4x_6 \leq 600 \\
			& x_1, x_2, x_3, x_4, x_5, x_6 \geq 0
		\end{array}
	\]
	Encontre todas as bases factíveis e depois a solução ótima por comparação.
	
	\begin{solution}
	Colocando o PL na forma padrão de minimização temos:
	\[
		\begin{array}{ll}
			\text{max} & -x_1 - 2x_2 - 4x_3 - 5x_5 - x_6 \\
			\text{sa } & 2x_1 + 6x_2 + 3x_3 + 2x_4 + 3x_5 + 4x_6 + x_7 = 600 \\
			& x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geq 0
		\end{array}
	\]
	Como temos apenas uma restrição a solução básica será formada por uma única variável.
	\begin{enumerate}
		\item $B = \{x_1 \} \rightarrow x_1 = 300 \rightarrow z = -300$;
		\item $B = \{x_2 \} \rightarrow x_2 = 100 \rightarrow z = -200$;
		\item $B = \{x_3 \} \rightarrow x_3 = 200 \rightarrow z = -800$;
		\item $B = \{x_4 \} \rightarrow x_4 = 300 \rightarrow z = 0$;
		\item $B = \{x_5 \} \rightarrow x_5 = 200 \rightarrow z = -1000$;
		\item $B = \{x_6 \} \rightarrow x_6 = 150 \rightarrow z = -150$;
		\item $B = \{x_7 \} \rightarrow x_7 = 600 \rightarrow z = 0$;
	\end{enumerate}
	Logo a solução ótima é $x_5 = 200$ e $x_1 = x_2 = x_3 = x_4 = x_6 = 0$.
	\end{solution}
	
	\item [3.6] Considere as restrições abaixo:
	\[
	\begin{array}{l}
		x_1 + 2x_2 \leq 6 \\
		x_1 - x_2 \leq 4 \\
		x_2 \leq 2 \\
		x_1, x_2 \geq 0
	\end{array}
	\]
	\begin{enumerate}
		\item Desenhe a região factível.
		
		\begin{solution}
		A região factível encontra-se representada na Figura~\ref{fig:Ex3.6}.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=0.3,domain=-0.2:7.2]
			\fill[color=gray!20] (0,0) -- (0,3) -- (2,2) -- (2,0);
			
			\draw[very thin,color=gray] (-1.1,-5.1) grid (7.2,4.9);
			
			\draw[->] (-1.2,0) -- (7.6,0) node[right] {$x_1$};
			\draw[->] (0,-5.2) -- (0,5.2) node[above] {$x_2$};
			
			\clip (-1.2,-5.2) rectangle (18.2,6.2);

			\draw[color=blue] plot (\x,0.5*6-0.5*\x) node[below right] {$x_1 + 2x_2 = 6$};
			\draw[color=red] plot (\x,-4+\x) node[right] {$x_1 - x_2 = 4$};
			\draw[color=green] plot (2,2*\x-9) node[right] {$x_1 = 2$};

			\end{tikzpicture}
			\caption{Região factível do exercício 3.6.} \label{fig:Ex3.6}
		\end{figure}
		\end{solution}
		
		\item Identifique os pontos extremos e para cada um identifique as variáveis básicas e não básicas.
		
		\begin{solution}
			Vamos colocar as restrições na forma padrão:
			\[
			\begin{array}{l}
				x_1 + 2x_2 + x_3 = 6 \\
				x_1 - x_2 + x_4 = 4 \\
				x_2 + x_5 = 2 \\
				x_1, x_2, x_3, x_4, x_5 \geq 0
			\end{array}
			\]
			Podemos então listar os pontos extremos e identificar as variáveis básicas (as demais são não básicas):
			\begin{enumerate}
				\item $(0,0)$: as variáveis básicas são $x_3$, $x_4$ e $x_5$.
				\item $(0,3)$: as variáveis básicas são $x_2$, $x_4$ e $x_5$.
				\item $(2,2)$: as variáveis básicas são $x_1$, $x_2$ e $x_4$.
				\item $(2,0)$: as variáveis básicas são $x_1$, $x_3$ e $x_4$.
				\item $(\frac{14}{3}, \frac{2}{3})$: as variáveis básicas são $x_1$, $x_2$ e $x_5$.
				\item $(4,0)$: as variáveis básicas são $x_1$, $x_3$ e $x_5$.
				\item $(6,0)$: as variáveis básicas são $x_1$, $x_4$ e $x_5$.
				\item $(-2,-2)$: as variáveis básicas são $x_1$, $x_2$ e $x_3$.
				\item $(0,-4)$: as variáveis básicas são $x_1$, $x_3$ e $x_5$.
			\end{enumerate}
		\end{solution}
		
		\item Suponha que deixa-se o ponto extremo $(4,0)$ para ir ao ponto extremo $(\frac{14}{3}, \frac{2}{3})$. Especifique quais variáveis entrão e quais deixam a base.
		
		\begin{solution}
			A variável que entra na base é $x_2$ e a que sai da base é $x_3$.
		\end{solution}
	\end{enumerate}
	
	\item [3.7] Considere o poliedro costituido pelos pontos $(x_1,x_2)$ tal que $x_1 + x_2 \leq 1$. Verifique que este poliedro não possue ponto extremo. Depois formule um poliedro equivalente de dimensão maior que possua pontos extremos.
	
	\begin{solution}
		É fácil verificar que o poliedro não possue pontos extremos pois é formado de uma única desigualdade e pontos extremos são formados pela intersecção de igualdades (em um espaço de dimensão $n$ é preciso, no mínimo, $n$ igualdades para caracterizar um ponto extremo).
		
		O poliedro definido por
		\[
			\begin{array}{l}
				x_1^+ + x_1^- + x_2^+ + x_2^- + x_3 = 1 \\
				x_1^+, x_1^-, x_2^+, x_2^-, x_3 \geq 0
			\end{array}
		\]
		possue pontos extremos e é equivalente o poliedro inicial.
	\end{solution}
	
	\item [3.8] Mostre que, na ausência de degenerância, existe uma correspondência um-para-um entre base factível e ponto extremo.
	
	\begin{solution}
		
	\end{solution}
	
	\item [3.9] Cosidere o sistema
	\[
		\begin{array}{l}
			x_1 + x_2 \leq 2 \\
			-x_1 + 2x_2 \leq 3 \\
			x_1, x_2 \geq 0
		\end{array}
	\]
	O ponto $(\frac{1}{2}, \frac{1}{2})$ é factível. Verifique qual a base relacionada com este ponto. Caso não exista tal base encontre uma base factível.
	
	\begin{solution}
		Vamos reescrever o sistema na forma padrão:
		\[
		\begin{array}{l}
			x_1 + x_2 + x_3 = 2 \\
			-x_1 + 2x_2 + x_4 = 3 \\
			x_1, x_2, x_3, x_4 \geq 0
		\end{array}
		\]
		É trivial notar que a solução $x_1 = x_2 = \frac{1}{2}$ não é básica. Uma base factível é $x_1 = x_2 = 0$, $x_3 = 2$ e $x_4 = 3$.
	\end{solution}
	
	\item [3.10] Resolva o PL
	\[
		\begin{array}{ll}
			\text{max } & 5x_1 + 4x_2 \\
			\text{sa } & x_1 + 2x_2 \leq 6 \\
			& 2x_1 - x_2 \leq 4 \\
			& 5x_1 + 3x_2 \leq 15 \\
			& x_1, x_2 \geq 0
		\end{array}
	\]
	\begin{enumerate}
		\item Graficamente.
		
		\begin{solution}
		A região factível encontra-se representada na Figura~\ref{fig:Ex3.10}.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=0.3,domain=-0.2:7.2]
			\fill[color=gray!20] (0,0) -- (0,3) -- (1.7,2.2) -- (2.4,0.9) -- (2,0);
			
			\draw[very thin,color=gray] (-0.2,-7.1) grid (7.2,10.9);
			
			\draw[->] (-0.2,0) -- (7.6,0) node[right] {$x_1$};
			\draw[->] (0,-7.2) -- (0,11.2) node[above] {$x_2$};
			
			\clip (-1.2,-8.2) rectangle (18.2,11.2);

			\draw[color=blue] plot (\x,0.5*6-0.5*\x) node[below right] {$x_1 + 2x_2 = 6$};
			\draw[color=red] plot (\x,-4+2*\x) node[right] {$x_1 - x_2 = 4$};
			\draw[color=green] plot (\x,0.33*15 - 0.33*5*\x) node[right] {$x_1 = 2$};

			\foreach \z in {15,20,25}{
			\draw[color=black] plot (\x,0.25*\z - 0.25*5*\x) node[right] {$z = \z$};
			}

			\end{tikzpicture}
			\caption{Região factível do exercício 3.10.} \label{fig:Ex3.10}
		\end{figure}
		
		Pela Figura~\ref{fig:Ex3.10} é fácil verificar que a solução ótima é, aproximadamente, $(1.7,2.2)$.
		\end{solution}
		
		\item Pelo Método Simplex.
		
		\begin{solution}
			Vamos primeiro colocar o problema na forma padrão de minimização:
			\[
				\begin{array}{ll}
					\text{min } & -5x_1 - 4x_2 \\
					\text{sa } & x_1 + 2x_2 + x_3 = 6 \\
					& 2x_1 - x_2 + x_4 = 4 \\
					& 5x_1 + 3x_2 + x_5 = 15 \\
					& x_1, x_2, x_3, x_4, x_5 \geq 0
				\end{array}
			\]
			O tableau inicial é
			\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline -5.0000 & -4.0000 & 0.0000 & 0.0000 & 0.0000 & 0.0000 \\
\hline 1.0000 & 2.0000 & 1.0000 & 0.0000 & 0.0000 & 6.0000 \\
\hline 2.0000 & -1.0000 & 0.0000 & 1.0000 & 0.0000 & 4.0000 \\
\hline 5.0000 & 3.0000 & 0.0000 & 0.0000 & 1.0000 & 15.0000 \\
\hline
\end{tabular}
\end{table}

A variável $x_1$ entra na base e a variável $x_4$ sai da base.
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline 0.0000 & -6.5000 & 0.0000 & 2.5000 & 0.0000 & 10.0000 \\
\hline 0.0000 & 2.5000 & 1.0000 & -0.5000 & 0.0000 & 4.0000 \\
\hline 1.0000 & -0.5000 & 0.0000 & 0.5000 & 0.0000 & 2.0000 \\
\hline 0.0000 & 5.5000 & 0.0000 & -2.5000 & 1.0000 & 5.0000 \\
\hline
\end{tabular}
\end{table}

A variável $x_2$ entra na base e a variável $x_5$ sai da base.
\begin{table}[!htb]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline 0.0000 & 0.0000 & 0.0000 & -0.4545 & 1.1818 & 15.9091 \\
\hline 0.0000 & 0.0000 & 1.0000 & 0.6364 & -0.4545 & 1.7273 \\
\hline 1.0000 & 0.0000 & 0.0000 & 0.2727 & 0.0909 & 2.4545 \\
\hline 0.0000 & 1.0000 & 0.0000 & -0.4545 & 0.1818 & 0.9091 \\
\hline
\end{tabular}
\end{table}

A variável $x_4$ entra na base e a variável $x_3$ sai da base.
\begin{table}[!htb]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline 0.0000 & 0.0000 & 0.7143 & 0.0000 & 0.8571 & 17.1429 \\
\hline 0.0000 & 0.0000 & 1.5714 & 1.0000 & -0.7143 & 2.7143 \\
\hline 1.0000 & 0.0000 & -0.4286 & 0.0000 & 0.2857 & 1.7143 \\
\hline 0.0000 & 1.0000 & 0.7143 & 0.0000 & -0.1429 & 2.1429 \\
\hline
\end{tabular}
\end{table}

Estamos no ótimo e a solução é $x_1 = 1.7143$, $x_2 = 2.1429$, $x_4 = 2.7143$ e $x_3 = x_5 = 0$.
		\end{solution}
	\end{enumerate}
	
	\item [3.11] Resolva o seguinte PL utilizando o Método Simplex e para cada iteração identifique $\mathbf{B}$ e $\mathbf{B}^{-1}$.
	\[
		\begin{array}{ll}
			\text{max} & 3x_1 + 2x_2 \\
			\text{sa } & 2x_1 - 3x_2 \leq 3 \\
			& -x_1 + x_2 \leq 5 \\
			& x_1, x_2 \geq 0
		\end{array}
	\]
	
	\begin{solution}
	Primeiramente vamos colocar o PL na forma padrão de minimização:
	\[
		\begin{array}{ll}
			\text{min} & -3x_1 -2x_2 \\
			\text{sa } & 2x_1 - 3x_2 + x_3 = 3 \\
			& -x_1 + x_2 + x_4 = 5 \\
			& x_1, x_2, x_3, x_4 \geq 0
		\end{array}
	\]
	
	O tableau inicial é
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline -3.0000 & -2.0000 & 0.0000 & 0.0000 & 0.0000 \\
\hline 2.0000 & -3.0000 & 1.0000 & 0.0000 & 3.0000 \\
\hline -1.0000 & 1.0000 & 0.0000 & 1.0000 & 5.0000 \\
\hline
\end{tabular}
\end{table}
de modo que
\[
	\mathbf{B} = \left[ \begin{array}{ll}
		1.0000 & 0.0000 \\
		0.0000 & 1.0000
	\end{array} \right], \mathbf{B}^{-1} = \left[ \begin{array}{ll}
		1.0000 & 0.0000 \\
		0.0000 & 1.0000
	\end{array} \right]
\]

	Escolhemos $x_1$ para entrar na base e $x_3$ para sair da base:
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline 0.0000 & -6.5000 & 1.5000 & 0.0000 & 4.5000 \\
\hline 1.0000 & -1.5000 & 0.5000 & 0.0000 & 1.5000 \\
\hline 0.0000 & -0.5000 & 0.5000 & 1.0000 & 6.5000 \\
\hline
\end{tabular}
\end{table}
\[
	\mathbf{B} = \left[ \begin{array}{ll}
		2.0000 & 0.0000 \\
		-1.0000 & 1.0000
	\end{array} \right], \mathbf{B}^{-1} = \left[ \begin{array}{ll}
		0.5000 & 0.0000 \\
		0.5000 & 1.0000
	\end{array} \right]
\]

	Escolhemos $x_2$ para entrar na base e não temos ninguém para retirar da base, logo a solução é ilimitada.
	\end{solution}
	
	\item [3.12] Resolva o PL pelo Método Simplex utilizando como base factível inicial $(x_1, x_2) = (4,0)$.
	\[
		\begin{array}{ll}
			\text{max } & -x_1 + 2x_2 \\
			\text{sa } & 3x_1 + 4x_2 = 12 \\
			& 2x_1 - x_2 \leq 12 \\
			x_1, x_2 \geq 0
		\end{array}
	\]
	
	\begin{solution}
		Vamos colocar o PL na forma padrão de minimização:
		\[
			\begin{array}{ll}
				\text{min } & x_1 - 2x_2 \\
				\text{sa } & 3x_1 + 4x_2 = 12 \\
				& 2x_1 - x_2 + x_3 = 12 \\
				x_1, x_2, x_3 \geq 0
			\end{array}
		\]
		
		Agora precisamos encontrar a base correspondente a $(x_1, x_2) = (4,0)$. Para isso precisamos determinar o valor das outras variáveis: $x_3 = 4$.
		
			O tableau inicial é
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|}
\hline 0.0000 & -0.6667 & 0.0000 & -4.0000 \\
\hline 1.0000 & 1.3333 & 0.0000 & 4.0000 \\
\hline 0.0000 & -3.6666 & 1.0000 & 8.0000 \\
\hline
\end{tabular}
\end{table}

A variável $x_2$ entra na base e a variável $x_1$ sai da base.
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|}
\hline 0.1000 & 0.0000 & 0.0000 & -1.9999 \\
\hline 0.7500 & 1.0000 & 0.0000 & 3.0000 \\
\hline 2.7499 & 0.0000 & 1.0000 & 18.9998 \\
\hline
\end{tabular}
\end{table}

Estamos no ótimo e a solução é $x_1 = 0.0000$, $x_2 = 3.0000$ e $x_3 = 18.9998$.
\end{solution}


	
	\item [3.29] Considere o PL
	\[
		\begin{array}{ll}
			\text{max } & 3x_1 + 2x_2 - x_3 + x_4 \\
			\text{sa } & 2x_1 - 4x_2 - x_3 + x_4 \leq 8 \\
			& x_1 + x_2 + 2x_3 - 3x_4 \leq 10 \\
			& x_1 - x_2 - 4x_3 + x_4 \leq 3 \\
			& x_1, x_2, x_3, x_4 \geq 0
		\end{array}
	\]
	Utilize o Método Simplex para verificar que a solução ótima é ilimitada. Faça uso do tableau final para construir uma solução cuja função objetivo tenha valor $\geq 3000$ e para encontrar uma direção $\mathbf{d}$ tal que $\mathbf{c}^T \mathbf{d} > 0$.
	
	\begin{solution}
	Escrevendo o problema na forma padrão de minimização:
	\[
		\begin{array}{ll}
			\text{min } & -3x_1 - 2x_2 + x_3 - x_4 \\
			\text{sa } & 2x_1 - 4x_2 - x_3 + x_4 + x_5 = 8 \\
			& x_1 + x_2 + 2x_3 - 3x_4 + x_6 = 10 \\
			& x_1 - x_2 - 4x_3 + x_4 + x_7 = 3 \\
			& x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geq 0
		\end{array}
	\]
	
	Fazendo $x_1$ entrar na base temos que $x_7$ sai da base:
	\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 0.0000 & -5.0000 & -11.0000 & 2.0000 & 0.0000 & 0.0000 & 3.0000 & 9.0000 \\
\hline 0.0000 & -2.0000 & 7.0000 & -1.0000 & 1.0000 & 0.0000 & -2.0000 & 2.0000 \\
\hline 0.0000 & 2.0000 & 6.0000 & -4.0000 & 0.0000 & 1.0000 & -1.0000 & 7.0000 \\
\hline 1.0000 & -1.0000 & -4.0000 & 1.0000 & 0.0000 & 0.0000 & 1.0000 & 3.0000 \\
\hline
\end{tabular}
\end{table}

Fazendo $x_3$ entrar na base temos que $x_5$ sai da base:
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 0.0000 & -8.1429 & 0.0000 & 0.4286 & 1.5714 & 0.0000 & -0.1429 & 12.1429 \\
\hline 0.0000 & -0.2857 & 1.0000 & -0.1429 & 0.1429 & 0.0000 & -0.2857 & 0.2857 \\
\hline 0.0000 & 3.7143 & 0.0000 & -3.1429 & -0.8571 & 1.0000 & 0.7143 & 5.2857 \\
\hline 1.0000 & -2.1429 & 0.0000 & 0.4286 & 0.5714 & 0.0000 & -0.1429 & 4.1429 \\
\hline
\end{tabular}
\end{table}

Fazendo $x_2$ entrar na base temos que $x_6$ sai da base:
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 0.0000 & 0.0000 & 0.0000 & -6.4615 & -0.3077 & 2.1923 & 1.4231 & 23.7308 \\
\hline 0.0000 & 0.0000 & 1.0000 & -0.3846 & 0.0769 & 0.0769 & -0.2308 & 0.6923 \\
\hline 0.0000 & 1.0000 & 0.0000 & -0.8462 & -0.2308 & 0.2692 & 0.1923 & 1.4231 \\
\hline 1.0000 & 0.0000 & 0.0000 & -1.3846 & 0.0769 & 0.5769 & 0.2692 & 7.1923 \\
\hline
\end{tabular}
\end{table}

Fazendo $x_5$ entrar na base temos que $x_3$ sai da base:
\begin{table}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 0.0000 & 0.0000 & 4.0000 & -8.0000 & 0.0000 & 2.5000 & 0.5000 & 26.5000 \\
\hline 0.0000 & 0.0000 & 13.0000 & -5.0000 & 1.0000 & 1.0000 & -3.0000 & 9.0000 \\
\hline 0.0000 & 1.0000 & 3.0000 & -2.0000 & 0.0000 & 0.5000 & -0.5000 & 3.5000 \\
\hline 1.0000 & 0.0000 & -1.0000 & -1.0000 & 0.0000 & 0.5000 & 0.5000 & 6.5000 \\
\hline
\end{tabular}
\end{table}

Fazendo $x_4$ entrar na base temos que ninguém sai da base de modo que temos solução ilimitada.
\end{solution}
\end{description}
